package Structures;

/**
 * 无向无环图
 * 邻接矩阵定义：m[i][j]=1表示存在边(i,j)，m[i][j]=0表示不存在从i到j的边；m[i][i]=1。
 */
public class UndirectedUnweightedGraph {

    /**
     * 求连通分量个数
     *
     * @param matrix 邻接矩阵
     */
    public static int computeNumConnectedComponents(int[][] matrix) {
        int nComponents = 0;
        int n = matrix.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                nComponents++;
                dfs(matrix, i, visited);
            }
        }

        return nComponents;
    }

    private static void dfs(int[][] matrix, int startVex, boolean[] visited) {
        visited[startVex] = true;
        int n = matrix.length;
        for (int j = 0; j < n; j++) {
            if (matrix[startVex][j] > 0 && !visited[j]) dfs(matrix, j, visited);
        }
    }
}
